نتائج البحث

Theories for Subexponential-size Bounded-depth Frege Proofs ...

• Authors : Ghasemloo, Kaveh; Cook, Stephen A.

Subjects: Computational Complexity Theory; Proof Complexity; Bounded Arithmetic

تفاصيل العنوان

CONSISTENCY PROOF OF A FRAGMENT OF PV WITH SUBSTITUTION IN BOUNDED ARITHMETIC

• Authors : Yoriyuki Yamagata

Subjects: FOS: Computer and information sciences; Discrete mathematics; Computer Science - Logic in Computer Science

• Source: The Journal of Symbolic Logic. 83:1063-1090

تفاصيل العنوان

Logical strength of complexity theory and a formalization of the PCP theorem in bounded arithmetic

• Authors : Ján Pich

Subjects: PCP theorem; Discrete mathematics; Computer Science - Computational Complexity

تفاصيل العنوان

Arithmetical definability and computational complexity

• Authors : Yassine Hachaïchi

Subjects: Discrete mathematics; General Computer Science; Computational complexity theory

• Source: Theoretical Computer Science. 322:137-146

تفاصيل العنوان

The ordering principle in a fragment of approximate counting

• Authors : Albert Atserias; Neil Thapen;

Subjects: Discrete mathematics; Bounded arithmetic; General Computer Science

• Source: UPCommons. Portal del coneixement obert de la UPCUniversitat Politècnica de Catalunya (UPC)Recercat. Dipósit de la Recerca de CatalunyaUniversitat Jaume I

تفاصيل العنوان

Theories with self-application and computational complexity

• Authors : Thomas Strahm

Subjects: Bounded applicative theories; Polynomial; Computational complexity theory

• Source: Information and Computation. 185:263-297

تفاصيل العنوان

Lower Bounds for DNF-refutations of a Relativized Weak Pigeonhole Principle

• Authors : Albert Atserias; Sergi Oliva; Moritz Müller ...

Subjects: Computational complexity theory; Logic; Upper and lower bounds

• Source: IEEE Conference on Computational ComplexityUPCommons. Portal del coneixement obert de la UPCUniversitat Politècnica de Catalunya (UPC)Recercat. Dipósit de la Recerca de

تفاصيل العنوان

On the Computational Complexity of Cut-Reduction

• Authors : Klaus Aehlig; Arnold Beckmann

Subjects: FOS: Computer and information sciences; Computer Science - Logic in Computer Science; Computational complexity theory

• Source: LICS

تفاصيل العنوان